1. Field of the Invention
The present invention relates to a highly safe server-aided computation system and method where a client requests a server to perform an arithmetic operation which does not depend on the client's secret.
2. Description of the Prior Art
In general, a public key cryptosystem is actively under investigation in order to obtain security of a communication information processing. The many public key cryptosystems such as an RSA system performs the following basic operation of modular exponentiation: EQU C=M.sup.d mod n (1)
where M denotes a plain text and d a secret exponent. The RSA system is called as such after the initials of the last names of three inventors thereof, Rivest, Shamlr and Adleman. Here, in order to secure the cryptosystem, a large number such as one with 512 bits length or more is generally used for each variable C, M, n and d. Therefore, steps for processing are significantly long, and when the arithmetic operations necessary for the steps is to be carried out by a system having a relatively slow processing speed, it takes a very long time to complete the operation.
Moreover, in the course of decoding the RSA cryptosystem, the exponent d must be kept secret in equation (1), so that care must be taken in dealing with the exponent when arithmetic operation is performed. It is convenient and safe on carriage that the d or n which serves as a key for decryption is stored in storage media such as an IC card or the like. However, in a case where an other system other than the IC card performs the exponentiation, the keys d and n must be sent to a system in which the modular exponentiation is operated, thus causing a possibility that the secret exponent d may be revealed to a third party. Moreover, though the modular exponentiation may be operated by a CPU (central processing unit) equipped in the IC card, it is difficult to achieve a practically fast processing time by the CPU equipped with the IC card since a capacity for numeric calculation in the IC card's CPU is very limited.
Therefore, conventionally proposed is that an auxiliary system is assigned for performing fast processing and keeping a secrecy on the exponent. This is called a server-aided secret computation method. Generally, the server-aided secret computation is executed by a system comprising three portions that are a client, a server and a communication line connecting the client and and the server. Among the calculation system, the client is a system which has a secret information regarding an object processing and is inferior to the server in the capacity of the arithmetic operation. The server executes a processing content requested by the client and sends back a result thereof to the client through the communication line. In the above processing, the server-aided secret computation method is such that a whole processing time is reduced by means of an auxiliary help from the server without revealing the secret information of the client to the third party. When the server-aided secret computation is configured using decryption system of the RSA cryptography, the exponent d in equation (1) is the secret information of the client.
As examples of the conventional server-aided computation protocols, there is a method proposed by Matsumoto et. al. ("Speeding up secret computation with insecure auxiliary devices", Proc. of Crypto 1988, Springer Lecture Notes in Computer Science, 408, pp. 497-506, 1988), and there is another revised and variation version by C. S. Laih et. al. (C. S. Laih et. al., "Two efficient server-aided secret computation protocols", proceeding of ASIACRYPT 1991). However, security of their protocols suggested by Matsumoto et. al. and Laih et. al. is unclear since transmitted messages between the client and the server are not perfectly independent of the secret exponent In order to possibly prevent the drawbacks in the above two examples, there is a method propose by Quisquater et. al. where the server's processing is made independent of the secret exponent (d) (J. J. Quisquater et. al. "Speeding up smart card RSA computations with insecure coprocessors", Smart Card 2000, Amsterdam 4-6, pp. 191-197, North Holland, Amsterdam, 1991). However, the method by Quisquater et. al. necessitates a huge volume of processing and communication in the client and the server, and there has been waited a further efficient technique to date.
As for a method where a modular exponentiation is realized with less number of modular multiplications there have been suggested various methods therefor. However, these methods differ in the server-aided secret computation in that the modular exponentiation is executed by both server and client and the object of these conventional methods do not lie in the fact that the exponent is revealed to no one but the client. Therefore, such conventional methods can not be applied to fulfill the objective of the server-aided computation.
Accordingly, in the conventional protocols such as one suggested by Matsumoto et. al., the security of the protocols is doubtful so that there is strong possibility that secret key might be revealed to the third party. Moreover, in the method employed by Quisquater et. al., there is far too much processing amount so that there is needed a much longer time for completing the arithmetic operation.